package acm;

import java.util.Scanner;

//把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？
//（用K表示）5，1，1和1，5，1 是同一种分法。
//Poj1664
public class MApplesAndNPlate {

	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		int count=scanner.nextInt();  //测试数据的数目
		int i=0;
		while (i<count) {
			int m=scanner.nextInt();
			int n=scanner.nextInt();
			if (n != 0) {
				int result = dispatchAppple(m, n);
				System.out.println(result);
			}
			i++;
		}
		scanner.close();
	}

	public static int dispatchAppple(int m,int n){
		if(m<0||n<0){
			System.err.println("您输入的数据有误"+n);
			return 0;
		}
		//先判断是否m<n，因为后面的结果都是基于M>=n的
		if(m<n){
			return dispatchAppple(m, m); //m<n，则S（m，n）=S（m，m）
		}
		//这个出口挺合情理的，但是在递归的过程中会出现问题
		//比如2个苹果2个盘子，等于0个苹果2个盘子，以及2个苹果1个盘子，按照这种思想第一个是等于0的
		//总的结果是1，而实际上结果为2
		//若两者中有一个为1，返回1 
//		if(m==1||n==1){
//			return 1;
//		}
//		if(m==0||n==0){
//			return 0;
//		}
		//考虑到m可能会出现0的情况，所以将m为0时return 1；
		//当n为0的时候，只要不是初始情况，一定有m也为0.比如2 2，就会有0,2，然后是0.0
		if(m==0||n==1){
			return 1;
		}
		return dispatchAppple(m-n, n)+dispatchAppple(m, n-1);
	}
	//上面一种解法采用的是递归的思想，而且包含了重复运算，导致时间复杂度很高
	//下面采用循环的方式实现
	//可是并不简单，还得用到栈，还是不做了
	/*public static int dispatchAppple(int m,int n){
		if(m<0||n<0){
			System.err.println("您输入的数据有误");
			return 0;
		}
		int result=0;
		while()
		return result;
	}*/
	
}
